package com.Algorithm.Study.ThinkTest;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2021/10/07/23:32
 * @Description: 在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对。
 * @Target: 逆序对问题
 */
public class ReverseSortGroup {

    // 896513   -- 逆序对 86 85 83 96 95 91 93  65 61 63  51 53


    public static void process(int arr[], int L, int R){

        while (L==R){
            return;
        }
        // 定::要在每一次操作排序时,将右边大于左边的次数统计,并求和
        int M = L + (R-L)>>1;

                process(arr,L,M);
                        process(arr,M+1,R);
                        merge(arr,L,M,R);  // 非叶子节点的都得运行

    }


    public static int merge(int[] arr, int L, int M, int R){
        // ----L----M---    ---M+1----R-----
        int p1=L;
        int p2=M+1;
        int help[] = new int[R-L+1];
        int i = 0;
        int res = 0;


        while (p1<=M&&p2<=R){
            // 135789  246789
            res+=arr[p1]>arr[p2]?(M-p2+1):0;
            help[i++]=arr[p1]<arr[p2]?arr[p1++] : arr[p2++];
        }




        while (p1<=M){
            help[i++]=arr[p1++];
        }


        while (p2<=R){
            help[i++]=arr[p2++];
        }


        for (int j = 0; j < help.length; j++) {
            arr[L+j]=help[j];
        }
        return res;


    }


}
